import reda.helpers.Helper;

/**
 * 
 */

/**
 * @author reda
 *
 */
public class MergeSort2 {
	
	
	public int[] mergeSort(int[] A){
		int n = A.length;
		if(n<=1){
			return A;
		}
		int[] result = new int[n];
		int median = n/2;
		int[] B = new int[median];
		int[] C;
		if(n%2==0){
			C = new int[median];
		}else{
			C = new int[median+1];
		}
		for(int i=0;i<median;i++){
			
			B[i]=A[i];
			//System.out.println(B[i]);
		}
		for(int j=0;j<C.length;j++){
			//System.out.println("----"+n+"----"+j + "---"+C.length);
			C[j]=A[median+j];
			//System.out.println(C[j]);
		}
		B=mergeSort(B);
		//System.out.println(B[0]);
		C=mergeSort(C);
		//System.out.println(C[0]);
		result=merge(B,C);
		
		
		
		
		return result;
	}

	/**
	 * Merge
	 */
	private int[] merge(int[] subA, int[] subB){
		int sizeResult = subA.length + subB.length;
		int[] result = new int[sizeResult];
		int i=0,j=0,k=0;
		while(i<subA.length && j<subB.length){
			while(i<subA.length && j<subB.length && subA[i]<=subB[j]){
				result[k]=subA[i];
				i++;
				k++;
			}
			while(j<subB.length && i<subA.length && subB[j]<subA[i]){
				result[k]=subB[j];
				j++;
				k++;
			}
			
			
		}
		if(i<subA.length){
			while(i<subA.length ){
				result[k]=subA[i];
				i++;
				k++;
			}
		}
		if(j<subB.length ){
			while(j<subB.length  ){
				result[k]=subB[j];
				j++;
				k++;
			}
		}
		return result;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] inputArray = Helper.generateArray(50);
		System.out.println("Before Sort");
		MergeSort2 m = new MergeSort2();
		Helper.printer(inputArray);
		int[] result = m.mergeSort(inputArray);
		System.out.println("\n After Sort");
		Helper.printer(result);
	}
}
